package datastructure.linked;

import java.util.function.Consumer;

/**
 * 带哨兵节点的单链表
 *
 * @author 杨 强
 * @package datastructure.linked
 * @createTime 2023-03-12 15:17
 */
public class SinglyLinkListSentinel {

    /**
     * 头节点,并且初始化为哨兵头节点
     */
    private Node head = new Node(666, null);

    public static void main(String[] args) {
        SinglyLinkListSentinel singlyLinkListSentinel = new SinglyLinkListSentinel();
        // 添加头节点
        singlyLinkListSentinel.addFirst(1);
        singlyLinkListSentinel.addFirst(2);
        singlyLinkListSentinel.addFirst(3);
        singlyLinkListSentinel.addFirst(4);
        // 遍历
        singlyLinkListSentinel.recursionLoop(value -> System.out.println(), value -> System.out.println());
        // 查找
        System.out.println(singlyLinkListSentinel.get(3));
        // 指定索引插入
        singlyLinkListSentinel.insert(0, 0);
        System.out.println(singlyLinkListSentinel);
    }

    /**
     * 往头部添加节点
     *    带哨兵的头节点需要跳过,也就是头节点是哨兵节点的下一个节点
     * @param value
     */
    public void addFirst(int value) {
        // 把添加节点作为头部节点, 然后下一个下一个节点指向以前的头部节点.
        this.head.next = new Node(value,this.head.next);
        // 或者调用
        // insert(0, value);
    }

    /**
     * 往尾部添加节点
     * @param value
     */
    public void addLast(int value) {
        // 查找最后一个节点
        Node last = findLast();
        // 最后一个节点的下一个节点指向新的节点
        last.next = new Node(value, null);
    }

    /**
     * 删除索引位置节点
     * @param index 索引
     */
    public void remove(int index) {
        // 查找到要删除节点的上一个节点
        Node prev = findNode(index - 1);
        if (prev == null){
            throw illegalIndex(index);
        }
        // 找到被删除的节点, 也就是需要删除节点的下一个节点
        Node removeNode = prev.next;
        if (removeNode == null){
            throw illegalIndex(index);
        }
        // 删除节点的上一个节点的下一个节点指向删除节点的下一个节点,那么这个删除就被移除指针了
        prev.next = removeNode.next;
    }

    /**
     * 向指定索引位置插入值
     * @param index 索引位置
     * @param value 值
     */
    public void insert(int index, int value) {
        // 找到索引位置的上一个节点
        Node prev = findNode(index - 1);
        if (prev == null) { // 找不到
            throw illegalIndex(index);
        }
        prev.next = new Node(value, prev.next);
    }

    /**
     * 根据索引查找节点
     * @param index 索引
     * @return 节点的值
     */
    public int get(int index) {
        Node node = findNode(index);
        if (node != null) {
            return node.value;
        }
        throw illegalIndex(index);
    }

    /**
     * 遍历-递归方式
     *      有哨兵头节点的链表的遍历需要从哨兵头节点的下一个节点开始遍历
     * @param before
     * @param after
     */
    public void recursionLoop(Consumer<Integer> before, Consumer<Integer> after){
        recursion(head.next, before, after);
    }

    /**
     * 查找链表的尾节点
     * @return
     */
    private Node findLast() {
        Node curr;
        for (curr = this.head; curr.next != null; curr = curr.next) { }
        return curr;
    }


    /**
     * 编写递归函数,做的事就是遍历节点需要做的事情, 针对某个节点的操作
     * @param node 遍历的每个节点
     * @param before 遍历节点前做的操作
     * @param after 遍历节点后做的操作
     */
    private void recursion(Node node, Consumer<Integer> before, Consumer<Integer> after){
        // 当节点为空退出循环
        if (node == null){
            return;
        }
        before.accept(node.value);
        System.out.println(node.value);
        after.accept(node.value);

        // 继续递归
        recursion(node.next, before, after);
    }


    /**
     * 根据索引找到节点
     *      需要跳过哨兵头节点
     * @param index
     * @return
     */
    private Node findNode(int index) {
        // 设置为-1, 就是从哨兵开始找
        int i = -1;
        for (Node curr = this.head; curr != null; curr = curr.next, i++) {
            if (index == i) {
                return curr;
            }
        }
        // 没有找到
        return null;
    }

    /**
     * 找不就报错
     */
    private IllegalArgumentException illegalIndex(int index) {
        return new IllegalArgumentException(String.format("index [%d] 不合法%n", index));
    }

}